package uk.org.landeg.euler.problems;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

import uk.org.landeg.euler.problems.framework.AbstractProblem;
import uk.org.landeg.euler.problems.framework.ProblemLauncher;
import uk.org.landeg.euler.problems.lib.CombinationGenerator;
import uk.org.landeg.euler.problems.lib.NumbersLib;
import uk.org.landeg.euler.problems.lib.PrimeLib;

public class Problem041 extends AbstractProblem {
	public static void main(String[] args) {
		ProblemLauncher launcher = new ProblemLauncher(new Problem041());
		launcher.solve();
//		CombinationGenerator gen = new CombinationGenerator(new int[] {1,2,3,4,5});
//		for (int n = 0 ; n < 120 ; n++) {
//			System.out.println(Arrays.toString(gen.getCombination(n)));
//		}
	}

	@Override
	public String getDescription() {
		return "What is the largest n-digit pandigital prime that exists?";
	}

	@Override
	public Integer getProblemNumber() {
		return 41;
	}

	@Override
	public Object solve() {
		notes.add("Pandigitals must use all numbers, for 9 digit, S(1..9) = 45 - divisible by 9 (none of these are prime)");
		notes.add("For 8 digit S(1..8) = 36 - always divisible by 3");
		notes.add("For 7 digit S(1..7) = 29 - this is our search range");
		notes.add("Generate a list of all 7 digit pandigitals and check for primes");
		CombinationGenerator gen = new CombinationGenerator(new int[] {1,2,3,4,5,6,7});
		long max = 7654321;
		notes.add("Max value is " + max);
		ArrayList<Long> primes = PrimeLib.seqPrimes(max);
		notes.add(primes.size() + " primes discovered");
		long value; long scale; int[] combination;
		long maxCombination = NumbersLib.factorial(7) - 1;
		Set<Long> candidates = new HashSet<Long>();
		for (int n = (int)maxCombination ; n > 0 ; n--) {
			scale =1;
			value = 0;
			combination = gen.getCombination(n);
			for (int x = combination.length -1 ; x >= 0 ; x--) {
				value += scale * combination[x];
				scale *=10;
			}
//			System.out.println(Arrays.toString(combination));
//			System.out.println(value);
			if (primes.contains(value)){
				candidates.add(value);
			}
		}
		long maxCandidate = 0;
		for (long l : candidates) {
			maxCandidate = (l > maxCandidate) ? l : maxCandidate;
		}
		return maxCandidate;
	}
}
